#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f, mod = 1e9 + 7;

int n, A;
string L, R, s;
int f[N][10][2][2];
int st[10];

int dfs(int pos, int j, int lead, int limit)
{
    if (pos == 0) return j == A;
    if (f[pos][j][lead][limit] != -1) return f[pos][j][lead][limit];
    int up = limit ? s[pos] - '0' : 9, res = 0;
    for (int i = 0;i <= up;i++) {
        if (j == A && st[i] == 0) continue;
        int pre = (i == 0 && lead) ? 0 : st[i] == 0;
        st[i]++;
        (res += dfs(pos - 1, j + pre, lead && i == 0, limit && i == s[pos] - '0')) %= mod;
        st[i]--;

    }
    f[pos][j][lead][limit] = res;
    return res;
}

bool check(string& t)
{
    set<char> cnt;
    for (int i = 1;i < t.length();i++)
        cnt.insert(t[i]);
    return cnt.size() == A;
}

void solve()
{
    cin >> n >> L >> R >> A;
    L += " ";R += " ";
    reverse(L.begin(), L.end());reverse(R.begin(), R.end());

    memset(f, -1, sizeof f);
    s = R;
    int ansR = dfs(n, 0, 1, 1);

    memset(f, -1, sizeof f);
    s = L;
    int ansL = dfs(n, 0, 1, 1);

    int ans = ansR - ansL + check(L);
    cout << (ans % mod + mod) % mod;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    std::istringstream in(R"()");
    std::cin.rdbuf(in.rdbuf());
#endif
    int T = 1;
    //cin>>T;
    for (int i = 1;i <= T;i++) {
        solve();
    }
}